using System;

namespace LeetCode {
    public class decoding {
        public int NumDecodings (string s) {
            if (s[0] == '0') return 0; //边界条件，如果第一位是字符0，那么完全不能解码，直接返回0
            int t1 = 1, t2 = 1, sum1, t3; //t1表示当前独立可合并下一位的个数，t2表示当前总的解码方式的个数
            for (int i = 1; i < s.Length; i++) //从第二位开始处理
            {
                sum1 = (s[i - 1] - '0') * 10 + s[i] - '0'; //如果跟前一位合并，计算合并之后的数值
                if (sum1 >= 1 && sum1 <= 26) //如果数值符合条件，那么可以合并
                {
                    if (s[i] != '0') //当前位不是0，那么t2加上t1的值，t1变成原本t2的值
                    {
                        t3 = t2;
                        t2 += t1;
                        t1 = t3;
                    } else //当前位是0，比如10这种情况，那么t2变成t1的值，t1清空
                    {
                        t2 = t1;
                        t1 = 0;
                    }
                } else //如果计算出来不能合并
                {
                    if (s[i] != '0') //如果当前位不是0，比如227，后面的27就不能合并，于是t2不变，t1变成t2的数值
                        t1 = t2;
                    else //如果当前位是0，又不能合并，比如30这种情况，那么直接返回0
                        return 0;
                }
            }
            return t2; //最终返回t2这个总的解码方式的个数
        }
        public int NumDecodings1 (string s) {
            int[] dp = new int[s.Length];
            int sum = 0;
            dp[0] = 1;
            sum = (s[0] - '0') * 10 + s[1] - '0';
            if (sum > 0 && sum < 10) {
                return 0;
            } else if (sum == 10) {
                dp[1] = 1;
            } else if (sum > 10 && sum < 20) {
                dp[1] = 2;
            } else if (sum == 20) {
                dp[1] = 1;
            } else if (sum > 20 && sum <= 26) {
                dp[1] = 2;
            } else if (sum > 26 & sum % 10 != 0) {
                dp[1] = 1;
            } else {
                return 0;
            }
            if (s.Length == 2)
                return dp[1];
            for (int i = 2; i < s.Length; i++) {
                sum = (s[i - 1] - '0') * 10 + s[i] - '0'; //如果跟前一位合并，计算合并之后的数值
                if ((sum > 10 && sum <= 26) && sum != 20) {
                    dp[i] = dp[i - 1] + dp[i - 2];
                } else if (sum == 10 || sum == 20) {
                    dp[i] = dp[i - 2];
                } else if ((sum > 0 && sum < 10) || (sum > 26 && sum % 10 != 0)) {
                    dp[i] = dp[i - 1];
                } else if (sum == 0 || sum % 10 == 0) {
                    return 0;
                }
            }
            return dp[s.Length - 1];
        }
        public int NumDecodings2 (string s) {
            if (s.Length == 0 || s[0] == '0') //边界情况
                return 0;
            int[] dp = new int[s.Length + 1];
            dp[0] = 1; //初始化
            dp[1] = 1;

            for (int i = 2; i <= s.Length; i++) {
                if (s[i - 1] == '0' && (s[i - 2] == '1' || s[i - 2] == '2')) //10和20两种情况
                    dp[i] = dp[i - 2];
                else if (s[i - 1] == '0') // 30,50等不符合条件的情况，直接返回0
                    return 0;

                else if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] - '0' <= 6) //12、26、24等情况
                    dp[i] = dp[i - 2] + dp[i - 1];
                else dp[i] = dp[i - 1];
            }
            return dp[s.Length];
        }
        public int NumDecodings3 (string s) {
            int[] f = new int[s.Length];
            char[] c = s.ToCharArray ();
            if (c.Length == 0) {
                return 0;
            }
            f[0] = c[0] > '0' ? 1 : 0;
            if (c.Length == 1) {
                return f[0];
            }
            int k = c[0] > '0' && c[1] > '0' ? 1 : 0;
            f[1] = k + (c[0] == '1' || c[0] == '2' && c[1] <= '6' ? 1 : 0);
            for (int i = 2; i < c.Length; i++) {
                if (c[i] > '0') {
                    f[i] += f[i - 1];
                }
                if (c[i - 1] == '1' || c[i - 1] == '2' && c[i] <= '6') {
                    f[i] += f[i - 2];
                }
            }
            return f[c.Length - 1];
        }
    }
}